package primary.sort_and_merge;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class FirstBadVersion {
    /*
        解法一，二分搜索，可以将true看作1，false看作0，所求位置就是0与1的交界处，数组中至少有一个1
        low左侧全都是0，high右侧全都是1
        如果mid所处位置是0，那么mid必然不会是所求位置，所求位置必然在mid+1及其右侧
        如果mid所处位置是1，那么mid可能是所求位置，通过增加low进行夹逼，直到low>=high,low就是所求位置
     */
    public int firstBadVersion(int n){
        int low = 1,high = n, mid = 0;
        while(low < high){
            mid = low + (high-low)/2;
            if(isBadVersion(mid)){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }
    boolean isBadVersion(int n){
        return true;
    }
}
